package Sort2017;

/**
 * 快速排序
 * Created by 雷文康 on 2017/12/26.
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array={9,7,8,6,5,4,3,2,1};
        quickSort(array);
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]);
        }
    }
    public static void quickSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        quickSort(array, 0, array.length - 1);
    }

    private static void quickSort(int[] array, int low, int high){
        if(low >= high){
            return;
        }
        int pos = partition(array, low, high);
        quickSort(array, low, pos-1);
        quickSort(array,pos+1, high);
    }

    private static int partition(int[] array, int low, int high){
        int val = array[low];
        while (low < high) {
            while (low < high && array[high] >= val) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= val) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = val;
        return low;
    }
}
